Skip to main content

Full text of "mit :: lcs :: tr :: MIT-LCS-TR-212"

See other formats



Digitalized Signatures 
and Public Key Functions 
as Intractable as Factorization 

Michael C. Rabin 

This blank page was inserted to preserve pagination. 



Michael 0. Rabin 

January 1979 



This empty page was substituted for a 
blank page in the original document. 


Michael 0. Rabin 

Visiting Professor of Applied Mathematics, MIT 
Professor of Mathematics, Hebrew University 
Jerusalem, Israel 

ABSTRACT . We introduce a new class of public-key 
functions involving a number n = p-q having two 
large prime factors. As usual, the key n is public, 
while p and q are the private key used by the 
issuer for production of signatures and function 
inversion. These functions can be used for all the 
applications involving public-key functions proposed 
by Diffie and Hellman [2], including digitalized 
signatures. We prove that for any given n, if we 
can invert the function y = E n (x) for even a small 
percentage of the values y then we can factor n . 
Thus as long as factorization of large numbers 
remains practically intractable, for appropriatly 
chosen keys not even a small percentage of signatures 
are forgerable. Breaking the RSA function [6] is 
at most as hard as factorization , but is not known to 
be equivalent to factorization even in the weak sense 
that ability to invert all function values entails 


ablllty to factor the key. Computation time for 
these functions, I.e. signature verification, is 
several hundred times faster than for the RSA scheme 
in [6]. Inversion time, using the private key, 
is comparable. The almost-everywhere Intractability 
of signature-forgery for our functions (on the 
assumption that factoring 1s intractable) is of 
great practical significance and seems to be the 
first proved result of this kind. 

Key words. Public-key functions, D1g1tal1zed 
signatures, Factorization, Intractable problems. 



In their fundamental paper [2] Diffie and 
Hellman have shown how public key trap door functions 
can be employed for the solution of various problems 
arising in electronic mail, including the production 
of digital ized signatures. An example of a public- 
key function usable for digitalized signatures was 
given in the elegant paper [6 ] by Rivest, Adelman, 
and Shamir, who introduced a trap-door one-way function 
employing a number n factorable into a product 
n = p-q of two large primes. The decoding algorithm 
given in [6] for this function requires knowledge 
of the factors p, q of n. It is, however, conceivable 
that another decoding algorithm exists that does not 
involve or imply factorization of n. Thus, breaking 
this one-way function is at most as difficult as 
factorization, but possibly easier. 

We present a different public key function which 
can be used for digitalized signatures, and all the 
other applications, in the same way as the above- 
mentioned function. The function in [6J is 1-1. 
Our function is four to one, but this causes only 
slight modifications in the applications. 


For this new function we can prove that the 
ability to forge signatures or decode messages 1s 
equivalent to the ability to factor large numbers. 
In fact, for any given n , a signature forgery or 
inversion algorithm effective in just a small 
percentage of all cases, say one case in a thousand, 
already leads to a factorization of n . By 
Inversion we mean finding for a number y in the 
range of E one of the x such that E(x) ■ y. 

In view of the present-day Intractability of 
the factorization problem, this fact lends substantial 
support to the viability of our public-key function. 
As long as it 1s Impossible in practice to factor 
large numbers, 1t will be Impossible for a fixed key 
to forge signatures even for a small percentage of 
all messages. 

The fact that we are able to prove, on the 
assumption that factoring is hard, that for our 
function, for a fixed key n whose factorization 
1s not given, Inversion must be hard for almost all 
messages 1s of great significance. For other trap 
door functions 1t may be the case that even though 
worst case complexity or even average complexity 
are high, in say one percent of cases Inversion 1s 


easy. From a commercial point of view this would pose 
an unacceptable risk. For example, an adversary can 
randomly search by computer for messages useful to 
him, such as payment instructions, on which he can 
forge signatures. To the best of our knowledge, we 
have in this article the first example of an almost 
everywhere difficult problem of this type. 

In addition, computation time for this function 
is several hundred times faster, and inversion 
when p,q are known, is about eight tlmesrfaster than 
the corresponding algorithms in [6]. If we Invert 
the RSA function by Chinese Remaindering, as we do 
here, then inversion time for the two functions are 

Theorems 1 and 2 concerning the equivalence of 
square-root extraction with factorization, are perhaps 
also of independent number-theoretic interest. 


Let n = p-q be the product of two large primes 
p,q, and let < b < n. 

DEFINITION 1: The function E p b (x) is defined for 
< x < n by E .(x) = x(x+b) mod n, < E n b (x)<n. 

Computation of E(x), for fixed n,b, requires 
one addition, one multiplication, and one division of 


x(x+b) by n to find the residue E b (x). Note 

that only the public key n,b, but not the factorization 

n = p-q, is required for encoding. 


Given c = x(x+b) modn, we want to find the 

four values < x. < n, 1 o < 4 such that Mx^) - c, 

We assume of course that the private key, i.e. the 
factors of n , are known. 

Throughout this paper res(A.B) will denote the 
residue of A when divided by B, and (A,B) will 
denote the greatest common divisor (g.c.d.) of A 
and B. 

The decoder, who is the issuer of the public 
key n,b, knows the factorization n = p*q. Clearly, 
it sufficies to solve the equation x(x+b) =c 
separately mod p and mod q and then find a solution 
mod n . 

Let a be an integer so that a = I mod p , 
a = mod q , and b satisfy b = 1 mod q, 
b = mod p . If r and s satisfy the congruence 
mod p and mod q respectively, then z = ar + bs 
solves the congruence mod n , and x = res (z,nj 
is the sought-after solution. 


In what follows let p be a fixed prime. We 
shall understand all integers a to be residues 
mod p, i.e., 0' <_ a < p . For d a quadratic 
residue (q.r.) modp, /a will denote any one of 
the two integers such that (/3) = mod p , and 
- /d will denote p - /d. 

To solve 
(1) f(x) = x + bx - c = mod p 

2 2 

let d ■ b/2 mod p then (x+d) = c + d mod p , 
x = - d t /c+d . We can solve the equation (1) 

as soon as we can extract square roots modp, i.e., 

solve y - m = mod p . 

Assume first that p = 4k - 1 so that 4|(p+l). 

Since m is a q.r., m 5 1 mod p. Weclaimthat 

(2) i - j/m = m mod p 

is one of the two square roots of m. Namely, 

l z = m = m«m = m mod p . 
Thus one implementation of the function would use p 
and q such that p = q = 3 mod 4, and the decoding algorithm 


For p =■ 4k + 1 we directly solve the equation (1) 
by a probabilistic algorithm. This is a special case of 
Berlekamp's root-finding 1n 6F(p) algorithm given in [1]. 


The short proof given here is taken from [5], where 
generalizations to GF(p n ) appear. If the roots of (1) 
are a, Be GF(p) then x 2 + b x - c = (x - a) (x - 3) The 

roots in GF(p) of the polynomial equation x -1=0 

are exactly the quadratic residues aeGF(p). Consequently, 

if a is a quadratic residue while 3 is not, then 

(x - 1, f(x)) = x - a, so that a and subsequently 
3 = -(b+a) mod p are readily found. 

Assume that a and 3 are of the same type , i.e., 
both quadratic residues (q.r.) or both quadratic non-resi- 
dues mod p, and that aj*3- Let < 6 < p then a + 5 and 
3+6 are of the same type if and only if (a+6)/(3+6) is 
a q.r. mod p. As 6 takes all values £ 6 < p except 
6 = -3, the quotient (a+6)/(B+6) takes all values 
<_ y < P except y = 1 . Thus for exactly ^— choices 
6, a+6 and 3+o will not be of the same type. 

Since f(x-6) = (x-ot-6) (x-a-3) » we have that for a 
Jiandom choice of < 6 < p, with probability 1/2 

(3) (x c -1, f(x-6)) = x-a-6 or x-3-6. 

Thus on the average two values of 6 have to be tried for 
finding the roots of (1). 

The computation of the g.c.d. (3) requires O(logap) 
operations in GF(p), i.e., additions and multiplications 


mod p. Namely, by essentially repeated squarlngs start- 
ing with x, compute x + h = res(x z , f(x-6)). Whenever 
a quadratic polynomial is encountered, divide by f(x-6) 
to produce a linear polynomial. Note that x is a formal 
variable so that all computations involve just pairs of 
residues mod p. Now by (3) , x + h - 1 is x - o - 6 or 
x - 3 - 6 , so that -6 - h + 1 is a root of (1). 


To employ E for signatures the signer P produces 
two large primes p,q by use of one of the prime-testing 
algorithms [3,7]. He forms n ■ p«q, chooses a number 
< b < n and publicizes the pair (n,b) (but not the 
factors p.q). 

By convention, when wishing to sign a given message, 
M,P adds as suffix a word U of an agreed upon length k. 
The choice of U 1s randomized each time a message is to 
be signed. The signer now compresses Mi * MU by a hash- 
ing function to a word C(Mi) = c, so that as a binary 
number c < n; see [4]. The computation of C( ) is publicly 
known, so that c - C(Mi) is checkable by everybody. 

P now checks whether for this c the congruence 

(4) x(x+b) = c mod n 


1s solvable. 

By the analysis of Section 2, this congruence 1s 
solvable if and only if m = c + d 2 is a q.r. mod p and 
mod q. Thus testing the solvability of (4) amounts to 
computing the Jacobi Symbols (^) and (-J) which is 
essentially a g.c.d. type computation. 

If congruence (4) is not solvable then P picks another 
random Ui and tries Ci ■ C(MUi). The expected number of 
tries is 4. When for some U the congruence (4) 1s 
solvable for c ■ C(MU), P finds a solution x. 

DEFINITION 2 : For a given public key n,b used by P and 
an agreed upon compressing function C( ) and Integer k, 
P's signature on a message M 1s a pair U,x where 
fc(U) = k and x(x + b) = C(MU) mod n. 

Anybody can check P's signature by computing 
c = C(MU) and testing whether x(x+b) = c mod n. 

The randomization of the suffix U of M also adds 
protection against possible attacks on the function E. 
Without the suffix, an adversary may attempt to feed to 
P messages M for his signature, hoping to learn the 
factorization of n from the solution of x(x+b) = C(M) 
mod n ,which will be produced by P as his signature. 
Actually, this does not seem a serious threat because of 
the hashing effected by C(M). 


However, the randomized suffix of length k leads 
to essentially 2 possible random values for c = C(MU). 
Thus for, say, k = 60, the adversary has no effective 
control over the congruence (4) that P will solve. 


We now want to show that 1f an adversary can invert 
E n . (x) by any algorithm then he can factor n. By invert- 
ing we mean finding for y one of the four x such that 
E n b^ = y * F"t nd1 ng one such x 1s sufficient for the 
would be signature forger, so that we want to show that 
this is hard. Thus the problem of, say, forging P's 
signilUFtl 1* exactly as intractable as the factorization 
of a number n which 1s a product of large primes. As 
mentioned in the Introduction, the scheme 1n [6] 1s at 
mo4t as safe as factorization but conceivably easier to 

In the following theorem we count an addition of num- 
bers a,b, <_ n as one operation. 

It is readily seen that 1f we can solve (4) for fixed 
n,b and arbitrary c then we can extract square roots, 
i.e., solve y 2 = m mod n whenever a solution exists. 
Namely, letting b = 2d mod n(n 1s odd) and m » c + d 2 
mod n, (4) turns into 


x 2 + 2dx + d 2 = (x+d) 2 = m mod n. 
Thus our result follows from 

THEOREM 1 : Let AL be an algorithm for finding one of 
the solutions of 

(5) y 2 = m mod n 

whenever a solution exists, and requiring F(n) steps. 
There exists an algorithm for factoring n requiring 
2F(n) + 21og 2 n steps. 

Vn.ooi. Assume that n - p*q 1s a product of two primes, 
the case relevant for E n b . The proof easily extends to 
the general case. 

For any < k < n, (k,n) - 1, there are exactly four 
solutions for the congruence 

y 2 = k 2 mod n. 

Namely, let res(k.p) = r, res(k.q) = s then the solutions 
y of this congruence satisfy res(y.p) = *r mod p.res(y.q) ■ 
= ±s mod q and each of the four sign combinations gives rise 
to a different solution. Defining for < yi,y 2 < n,yi*y 2 
to mean y? = y| mod n, we see that this equivalence relation 
decomposes the set < y < n, (y,n) ■ 1 into classes each 
containing four elements. 

Denote by /m the solution of (5) by AL for any 
m, (m,n) =1. If AL produces more than one solution then 


the factorization algorithm that follows is even further 
facil itated . 

Choose at random a number < k < n. If (k,n) + 1 
then we directly get a factor of n. In practice, this 
possibility can be neglected. Compute k 2 = m mod n. 

Compute k! = /m by AL . Now, k is i n the equi val ence 
class, by the relation a,, of k x . In a random choice of 
< k < n, all four possible choices of numbers within 
any class are equally likely. Hence with probability 1/2 


k = ki mod p, k = - ki mod q 
k = - ki mod p, k = ki mod q 

Therefore with probability 1/2 


(k-ki ,n) = p or q 

The computation of /m requires F(n) steps. The 
computation of the g.c.d. (6) requires at most log 2 n 
subtractions and divisions by 2, of numbers smaller than n, 
Hence the expected number of steps is 2F(n) + 2 log 2 n. 

If we count bit-operations then subtraction of numbers 
smaller than n requires at most log 2 n bit-operations 
and the bound is 2F(n) + 2(log 2 n) 2 . 

The previous theorem may be strengthened to cover the 
situation that for the given key E n b can be decoded in 
just a small percentage of all cases. 


THSOREM 2 : If AL solves (5) in F(n) steps for 1/e 
of the < m < n, . (m.n) * V, for which (5) has a solution, 
then there is an algorithm for factoring n requiring 
2eF(n) + 21og 2 n steps. 

Vfiooi. As in the proof of Theorem 1, choose a < k < n at 
random and compute k 2 = m mod n. Apply AL to find ,/m. 
If the computation runs more than F(n) steps abort it 
and choose another k. Whenever a root k a - /m is found, 
compute (k-ki.n). The analysis in the proof of Theorem 1 
implies that with probability 1/2 each such try produces 
a factorization of n. 

The expected number of choices of k leading to a /m 
is § »nd the expected number of 4ucce**(M of AL needed 
for a factorization, is 2. Thus the total expected number 
of steps is 2eF(n) + 21og 2 n. Note that we embark on the 
second phase of the factorization only after a success of 
AL in finding /m. 

If for example e = 1000, and F(n) were not prohibi- 
tively large, then an adversary, could factor n in 
2000 F(n) + 21og 2 n steps. Consequently, if no practical 
algorithm for factoring n is possible , then no practical 
decoding algorithm could work in even 1/1000 of all cases. 



The above method of construction of a one-way function 
can be extended to employ polynomials or powers of x of 
small degrees other than 2. 

Assume for example that n = p*q, where p and q 
are primes of the form 3k + l . The one-way function will 
be E(x) = x 3 mod n. The decoding 1s effected by solving 
x 3 - m e mod p and mod q by a probabilistic algorithm 
similar to the one used 1n Section 2. Again one can prove 
that any algorithm for extracting cubic roots leads, for n 
of the above form, to a factorization of n. 

The probability that x 3 = w mod n 1s solvable for a 
random w 1s 1/9. Thus for utilization ' In signatures the 
quadratic scheme seems best. 



[1] Berlekamp, E.R., Factoring polynomials over large 

finite fields, Math, of Coop., vol. 24 (1970), pp. 713-735. 

[2] Diffie, W. , and Hellman, M. , New directions in crypto- 
graphy, IEEE Trans, of Inf. Theory, IT-22, (November 1976), 
pp. 644-654. 

[3] Rabin, M. , O., Probabilistic algorithms, Algorithms 
and Complexity, Recent Results and New Directions, 
J. P. Traub, editor, Academic Press, New York, 1976, 
pp t 31*40, 

[4] Rabin,' M.O., Digitalized signatures, Foundations of 

Secure Computations, R. Lipton and R. DeMillo editors, 
Academic Press New York, 1978/ 

[5] Rabin, M.O., Probabilistic algorithms in finite fields, 
submitted for publication. 

[6] Rivest, R.L., Shamir A., and Adleman L. , A method for 
obtaining digital signatures and public-key crypto- 
sy 8 terns, Coram. ACM. vol. 21 (February 1978) . 

[7] Solovay, R. , and Strassen, V., A fast monte -carlo test 
for primality, SIAM Jour, on Comp. Vol. 6 (1977), 
pp. 84-85.